package com.srunpass.algorithm;

public class 地下城游戏 {

    Integer[][] res;
    int ilen, jlen;
    int[][] dungeon;

    public int calculateMinimumHP(int[][] dungeon) {
        ilen = dungeon.length;
        jlen = dungeon[0].length;
        res = new Integer[ilen][jlen];
        this.dungeon = dungeon;
        return gene(0,0);
    }

    int gene(int i, int j) {
        if(i == ilen - 1 && j == jlen - 1){
            return Math.max(1,-dungeon[i][j]-1);
        }
        if (i >= ilen || j >= jlen) {
            return Integer.MAX_VALUE;
        }
        if (res[i][j] != null) {
            return res[i][j];
        }
        res[i][j] = Math.max(1, Math.min(gene(i + 1, j), gene(i, j + 1))-dungeon[i][j]);
        return res[i][j];
    }
}
